#pragma once

// The file contains classes to support the basic operation of the TidyGraphGenerator

#include <utility>
#include <vector>
#include <set>
#include <ostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <list>
#include <string>
#include <gtest/gtest_prod.h>

using namespace std;
typedef unsigned int uint;

// define a new graph internal property type for girth
namespace boost
{
enum vertex_girth_t {vertex_girth};

BOOST_INSTALL_PROPERTY(vertex, girth);
} // namespace boost

namespace cccn {

struct GraphName_t 
  {
  GraphName_t () : name (), girth (0), sumGirth (0), avgDistance (0) {}

  // name of the graph
  string name;
  // the minimum girth
  uint girth;
  // the sum of all griths associated with each node
  uint sumGirth;
  // the average distance of all node-pairs
  double avgDistance;
  // the second smallest eigenvalue of the Lapican matrix
  double syncValue;
  // the ratio between the largest and the non-zero smallest eigenvalues of the Lapican matrix
  double syncRatio;
  };

/// The internal representation of a graph
typedef boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, 
  // vertex properties
  boost::property<boost::vertex_index_t, uint,
  boost::property<boost::vertex_girth_t, uint> >,
  // edge properties
  boost::property<boost::edge_index_t, uint>, 
  //boost::no_property,
  // graph properties
  GraphName_t> BoostGraph_t;

/// Testing function for the GeneratorSupport source code
void GeneratorSupportTest ();

/** 
 * Data structure of a bi-directional graph 
 */
class Graph
  {
  public:
    typedef pair<uint, uint> Edge_t;

    Graph ();

    /**
     * Conenct node a to node b bidirectionally
     * \param a node id
     * \param b node id
     * \return True if a new bi-directional link is added; false otherwise
     */
    bool Connect (uint a, uint b);

    /**
     * Remove the edge between node a and b, if there is any
     */
    void Disconnect (uint a, uint b);

    /// Get access to the internal boost graph data structure
    const BoostGraph_t& GetBoostGraph () const;
    BoostGraph_t& GetBoostGraph ();
    
  private:      
    /// The internal representation of a node
    typedef boost::graph_traits<BoostGraph_t>::vertex_descriptor Vertex_t;

    /// Add the vertex n into a graph if it is not yet added, and return the vertex
    Vertex_t AddVertex (uint n);

    /// The set of all edges contained in this graph
    BoostGraph_t m_graph;

    friend ostream& operator<< (ostream& os, const Graph& g);

    // for testing private methods
    FRIEND_TEST (GraphTest, AddVertexTest);
  };

/// \return the girth of the graph g
uint GetGirth (const Graph& g);

/// \return the number of nodes of the graph g
uint GetSize (const Graph& g);

/**
 * Measure various statistical properties of a given graph
 */
class GraphMeasure
  {
  public:
    /// Prepare to measure various statistical properties of a given graph g
    GraphMeasure (const Graph& g);
    /// Number of bi-directional edges in a graph g
    uint NumberOfEdges () const;
    /// Number of nodes in a graph g
    uint NumberOfNodes () const;
    /// Get all neighbors of node n
    list<uint> GetNeighborsOf (uint n) const;
    /// Get the node degree of a vertex n
    uint DegreeOf (uint n) const;

  private:   
    typedef boost::graph_traits<BoostGraph_t>::vertex_descriptor Vertex_t;

    const BoostGraph_t& m_graph;
  };

/// \return a random integer in the ranage [0, maxInt], including both 0 and maxInt
uint RandomInt (uint maxInt);

ostream& operator<< (ostream& os, const Graph::Edge_t& e);
ostream& operator<< (ostream& os, const Graph& g);

}; // namespace cccn
